"""
3209. 子数组按位与值为 K 的数目
困难
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个子数组满足：子数组中所有元素按位 AND 的结果为 k 。



示例 1：

输入：nums = [1,1,1], k = 1

输出：6

解释：

所有子数组都只含有元素 1 。

示例 2：

输入：nums = [1,1,2], k = 1

输出：3

解释：

按位 AND 值为 1 的子数组包括：[1,1,2], [1,1,2], [1,1,2] 。

示例 3：

输入：nums = [1,2,3], k = 2

输出：2

解释：

按位 AND 值为 2 的子数组包括：[1,2,3], [1,2,3] 。



提示：

1 <= nums.length <= 105
0 <= nums[i], k <= 109
"""
from typing import List
import bisect

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        #    print(Solution().countSubarrays([0,8,0,8,5],8)) # 2
        ans = 0
        for x,y in enumerate(nums):
            if y==k:
                ans+=1
            for z in range(x-1,-1,-1):
                #无意义，是前面所有的父级，往前继续and也只是原结果
                if y & nums[z] == nums[z]:
                    #如果是父级，则找到前面当前满足k的，多加上当前算一个新的集合，多算一次
                    # ans += nums[0:z+1].count(k)
                    # 优化：使用二分查找统计k的出现次数，因为nums[0，z]是升序的否则会超时
                    left = bisect.bisect_left(nums, k, 0, z + 1) #第一个出现位置
                    right = bisect.bisect_right(nums, k, 0, z + 1) #最后出现位置+1
                    ans += right - left
                    break
                #计算当前结果
                nums[z] = y & nums[z]
                if nums[z]==k:
                    ans += 1
        return ans
    def countSubarrays_timeOut(self, nums: List[int], k: int) -> int:
        ans = 0
        for x,y in enumerate(nums):
            if y==k:
                ans+=1
            for z in range(x-1,-1,-1):
                #无意义，是前面所有的父级，往前继续and也只是原结果
                if y & nums[z] == nums[z]:
                    #如果是父级，则找到前面当前满足k的，多加上当前算一个新的集合，多算一次
                    for p in range(z,-1,-1):
                        if nums[p] == k:
                            ans+=1
                        elif nums[p]<k:
                            break
                    break
                #计算当前结果
                nums[z] = y & nums[z]
                if nums[z]==k:
                    ans += 1
        return ans
if __name__ == '__main__':
    # print(Solution().countSubarrays([1,1,1],1))
    print(Solution().countSubarrays([0,8,0,8,5],8)) # 2
    # print(Solution().countSubarrays([0,0,4,6,2],6)) #1

    nums = [1, 2, 2, 2, 3]
    k = 2
    left = bisect.bisect_left(nums, k)  # 返回 1 (第一个2的位置)
    right = bisect.bisect_right(nums, k)  # 返回 4 (最后一个2之后的位置)

    print(left)
    print(right)
    print(bisect.bisect_left(nums, 4) ) #找不到返回length
    print(bisect.bisect_left(nums, 4) ) #找不到返回length
    count = right - left  # 4 - 1 = 3 (正好是2的出现次数)